#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
	unsigned char *bits; // 用于存储bit的char数组 每一个char变量成员 表示八个bit
	size_t size;         // bitset的大小，即bit的个数
} bitset;

//初始化
bitset *bitset_init(size_t size) { //size的意思是bit的个数
	if ( size<=0 ){
		printf("[error]初始化失败。返回NULL。size应该是正整数。\n");
		return NULL;
	}
	if ( size>(size_t)1e8 ){
		printf("[error]初始化失败。返回NULL。qwq太大啦，要爆内存了。 \n");
		return NULL;
	}
	bitset *bs = (bitset *)malloc(sizeof(bitset)); //这里使用malloc，因为我后续会对bitset结构体的成员进行手动初始化
	if (bs == NULL) {
		printf("[error]初始化失败，返回NULL。未知错误:bitset结构体的存储空间 分配失败。\n");
		return NULL; // 分配失败
	}
	
	size_t array_size = (size + 7) / 8; // 每个char是8位，因此需要的字节数， 并且这种写法最多浪费7个bit，最少不浪费()
	bs->size = size;
	bs->bits = (unsigned char *)calloc(array_size, sizeof(unsigned char)); //这里使用calloc，让库函数帮我做初始化 所有的bit全部设置成0()
	if (bs->bits == NULL) {
		free(bs);
		printf("[error]初始化失败，返回NULL。未知错误:bitset结构体里面的chars数组的存储空间 分配失败。\n");
		return NULL; // 分配失败
	}
	return bs;
}


//置1
void bitset_set(bitset *bs, size_t index) {
	if ( index<0 ){
		printf("[error]修改失败。index应该是一个非负整数\n");
		return;
	}
	if (index >= bs->size) {
		printf("[error]修改失败。返回NULL。index太大啦，超出这个bs的范围了。 bs范围: %zu, 而你给的index是%zu。\n", bs->size, index);
		return; // 超出范围
	}
	bs->bits[index / 8] |= (1 << (index % 8)); //这里有个关键点， 这个1左移的位数小，对应的index是更小的
	//也就是说 每一个char变量存储的8个bit 对应的index 是从左到右减小的
}

/*
举个例子，假设某个bs一共有20个bit, 那么我要修改第19个bit 
首先 这个bit在bs->bits[2]
然后 bits[2]当中 从左到右的bit分别是 o o o o 0 o o o 
(这里的o是其他的bit，0是我要进行修改的第19个bit)
*/
  
//置0
void bitset_clear(bitset *bs, size_t index) {
	if (index >= bs->size) {
		return; // 超出范围
	}
	bs->bits[index / 8] &= ~(1 << (index % 8)); //这里有个关键点， 这个1左移的位数小，对应的index是更小的
	//也就是说 每一个char变量存储的8个bit 对应的index 是从左到右减小的
}


bool bitset_test(const bitset *bs, size_t index) {
	if (index >= bs->size) {
		return false; // 超出范围
	}
	return bs->bits[index / 8] & (1 << (index % 8));
}

void bitset_free(bitset *bs) {
	if (bs == NULL){
		printf("[error]释放失败。传了一个空指针。\n");
		return;
	}
	free(bs->bits);
	free(bs);
	
}

void bitset_print(bitset *bs){
	printf("[attention]qwq 这个是调试用的 bs开太大的话别用 输出流太多了也看不清\n");
	printf("[attention]注意了 每一个char变量存储的8个bit 对应的index 是从左到右减小的。这里的输出方向 是从左到右输出的\n");
	printf("[attention]我的这种写法最多浪费7个bit，最少不浪费。被浪费的bit则会输出X\n");
	if ( bs->size > 1000 ){
		printf("[warning]bs太大了 还是算了罢() 你开小点。这里不输出了。\n");
		return;
	}
	printf("[debug]----------↓输出测试↓----------\n");
	for ( size_t i=0; i <= (bs->size+7)/8 - 1; i++ ){
		printf("[%03zu - %03zu] ", i*8,i*8+7);
		for ( int j=0; j<=7; j++ ){
			bool this_bit = (bool) ( bs->bits[i] & (1 << (7-j)) ) ;
			if ( i*8+(7-j) < bs->size ) printf("%1d", this_bit);
			else printf("X");
			if ( j==3 ) printf(" ");
		}
		printf("\n");
	}
	printf("[debug]----------↑输出测试↑----------\n");
	
}


int main() { //测试一下
	bitset *bs = bitset_init( (size_t)25 ); //初始化全是0
	
	bitset_set(bs, 0);
	bitset_set(bs, 10);
	bitset_set(bs, 19);
	bitset_set(bs, 20);
	bitset_set(bs, 24);
	
	printf("Bit 19: %d\n", bitset_test(bs, 19)); // 应该输出 1
	printf("Bit 20: %d\n", bitset_test(bs, 20)); // 应该输出 1
	printf("Bit 24: %d\n", bitset_test(bs, 24)); // 应该输出 1

	
	printf("Bit 18: %d\n", bitset_test(bs, 18)); // 应该输出 0
	printf("Bit 22: %d\n", bitset_test(bs, 22)); // 应该输出 0
	
	bitset_print(bs);
	/* 应该输出 :
	0000 0001
	0000 0100
	0001 1000
	XXXX XXX1
	*/
	
	bitset_clear(bs, 10);
	printf("Bit 10 after clear: %d\n", bitset_test(bs, 10)); // 输出 0
	
	bitset_print(bs);
	/* 应该输出 :
	  0000 0001
	  0000 0000
	  0001 1000
	  XXXX XXX1
	 */
	
	bitset_free(bs);
	return 0;
}

